// start with one pass over the two trees that will mark
// for every node a pointer to its heaviest child.
// the to trees are F the larger one and G which is smaller in size

#ifndef __TED_H__
#define __TED_H__


#include <hash_map>
#include "Lse.h"
#include "Rse.h"
#include "Ilse.h"
#include "Irse.h"

using namespace std;

enum Algorithm {OPT=0, KLIEN=1 , SHASHA_ZHANG=2};
enum Strategy {LEFT, RIGHT, BOTH};

int Minimum(const int a,const int b,const int c);

class TED
{
	Tree* F;
	Tree* G;
	bool initReverse;
	int **delta	;	//distance between all rootless trees
					//indexed according to the postorder of the trees
					//takes use of the mapping GetTree[2] defined at tree.h
	Algorithm algorithm;
	int result;
	Distance* distance;//distance metric configuration
	Lse* startLse;
	Rse* startRse;

public:
	TED(Tree* F1,Tree* G1, Distance* distance1, Algorithm algorithm1);
	~TED();
	
	void TED_pro(Tree *F1,Tree *G1, bool reversed);
	void ComputePeriodMain(Tree* F1, Tree* G1, bool reversed);
	void ComputePeriodRec(Tree* F1, Tree* G1, bool reversed, vector<int>* T, Strategy dir, Lse& leftSubForestEnum, Rse& rightSubForestEnum);
	void ComputePeriod(Tree* Fvp, Tree* G1, bool reversed, vector<int>* T, Strategy dir,Lse& leftSubForestEnum, Rse& rightSubForestEnum, bool FirstSideOf2);


	void PrecomputeT(vector<int>* T, Lse& lse);
//	int GetDistance(int i1,int i2,int i3,int i4);
	int GetTED(){return result;}
	
};



#endif //__TREE_H__